package com.zhu.algorithm.sort;

import com.zhu.algorithm.sort.impl.Sort;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 *
 * @Author: zhujiabao
 * @Date: 2021/12/24/15:14
 * @Description:希尔排序（采用希尔增量）(采用移动法，而非交换法)
 *
 * 算法步骤
 *
 * 选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
 *
 * 按增量序列个数 k，对序列进行 k 趟排序；
 *
 * 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
 */
public class ShellSort  implements Sort {

    @Override
    public int[] sort(int[] sourceArray) {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        long A=System.currentTimeMillis();

        //用希尔增量
        int grep = arr.length/2;
        int k = 0;
        //每次增量变化校验一次
        while (grep>0){
            //这里相当于是插入排序
            for (int i=grep+k; i<arr.length;i=i+grep){
                int temp = arr[i];
                int j = i;
                while (j>=grep && temp<arr[j-grep]){
                    arr[j] = arr[j-grep];
                    j = j-grep;
                }
                if (j!=i)
                    arr[j] = temp;
            }

            //如果超过了grep那么就重新来
            if (k<grep){
                k++;
            }else {
                k=0;
                grep=grep/2;
            }
        }


        long B=System.currentTimeMillis();
        System.out.println("希尔排序所耗时间： "+(B-A)+"ms");

        return arr;
    }
}
